package Top_Interview_Questions_Review._012Backtracking;

import java.util.LinkedList;
import java.util.List;

/**
 * @Author: 吕庆龙
 * @Date: 2020/4/12 16:51
 * <p>
 * 回溯--组合
 */
public class Summary_0077 {

    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(n, 1, k, track);
        return res;
    }

    public void backtrack(int n, int start, int k, LinkedList<Integer> track) {
        if (k == track.size()) {
            res.add(new LinkedList<>(track));
            return;
        }

        for (int i = start; i <= n; i++) {
            //选择路径
            track.add(i);
            backtrack(n, i + 1, k, track);
            //撤销刚刚的路径选择。
            track.removeLast();

        }
    }
}
